System-controlling queues are commonly used in past and current data processing systems. Some queues have been managed by hardware logic circuitry and other queues have been managed by programmed or micro-programmed routines. A large number of queues are commonly used by system control programs to control the reusable hardware and software resources of a data processing system, including queues which are themselves system resources. Dispatching queues have been commonly used in the prior art.
Of foremost importance with any system-controlling queue is that the integrity of the queue must always be maintained. The integrity problem becomes more difficult as the number of central processors increases and the number of users increases in a large system in which the CPUs contend asynchronously for resources in the system.
Each queue is generally comprised of a plurality of entries (often called "elements") in which each element is a unit of the queue. For example, each element of a queue may represent a different waiting request for an I/O device in a system. The queue elements may be dequeued when the requested device is started. At any given time the queue may have anywhere from no elements (indicating no I/O request is waiting for an I/O device) to a large number of elements (indicating a large number of I/O requests are waiting for service).
Another example is a dispatching queue used to receive all user requests for the execution of a user program. Elements on the queue are associated with the different user program task requests and indicate which user task requests are ready to be executed by a CPU so they can be dispatched.
Queues may be classified into several general types according to the relative locations of the elements in the queue; and they are: (1) contiguous queues with elements physically located next to each other, (2) linear chained queues with elements physically dispersed anywhere in main or virtual storage (MS or VS), and (3) hierarchical chained queues that speed up queue operation by using hierarchical searching.
All queues have an anchor (header) at a predetermined location in storage for providing an entry point into the queue. The anchor contains an address (called an anchor pointer) which addresses one end of a chain of variable elements comprising the queue. Each element may contain a pointer to a next element in the queue and be a single threaded queue, or each element may contain backward and forward pointers and be a double threaded queue. The last element in the queue chain has an indicator code (often all zeroes) in its pointer location to identify it as the last element. If there is no variable element currently in the queue (i.e. the queue is empty), the anchor pointer contains an empty code (e.g. all zeroes).
Elements may be inserted (added) into, or deleted from, a chained single-threaded queue. The easiest and fastest insertion and deletion is of the anchor pointed element, which is done by changing the anchor pointer itself. Insertion of a new element between two existing elements in the queue involves moving the pointer field in the prior element into the pointer field in a new element, and putting the address of the new element into the pointer field of the prior element in the queue. Deletion of an element from the queue involves moving the pointer field in the deleted element into the pointer field in its prior element.
A chained queue may be a last-in/first-out (LIFO) queue, a first-in/first-out (FIFO) queue, an ordered queue, or some other type of non-LIFO organization. The subject invention is primarily directed to the environment of chained hierarchical queue operations requiring the ordering of elements in accordance with values in their priority fields.
The simplest queues use LIFO operations which always insert and delete each new element next to the anchor in a queue. Thus, the anchor pointed element is always the newest and last element in a pure LIFO queue. However, many data processing activities cannot use LIFO queue operation and require FIFO, ordered, or some other type of dequeueing selection.
Multiprocessing (MP) systems have two or more processors, e.g. CPUs that can simultaneously and asynchronously be executing separate instruction streams in relation to a shared main storage (MS). MP has been recognized in the prior art to present special queue problems. For example, it has been recognized that it is undesirable for any processor to take action based on an incompleted change in the queue by another processor. This would adversely affect the integrity of the queue and of information obtained therefrom. For example, this could happen if a second processor attempts to change an element in a queue while a first processor is changing the same element in the queue. System deadlock and failure can result.
The prevention of asynchronous changes in queue elements has been supported by the atomic operation of the S/370 Test and Set (TS) or Compare and Swap (CS or CDS) instruction operation on a queue lock field to prevent MP conflict in changing the queue. The atomic instruction operation assures that only one program at a time will change the content of a selected part of a queue.
Maintaining queue integrity has required the use of coordinating conventions among all programs using a queue by requiring all programs to voluntarily check the state of certain fields by using the atomic instructions to make changes to the queue, such as to a lock field, and honor its state before attempting to change the queue.
MP queue conflict has been generally solved in different ways in the prior art. One prior solution associates a lock field with the anchor of the queue to enable serialization of all accesses to the queue which may change the queue, so that only one program will access the queue to change it at any given time. Other programs seeing the lock is set on will avoid trying to change the queue. When any queue accessing program is done changing the queue, it changes the lock field to indicate an unlocked state, so that it will appear in unlocked state to the next program desiring to use the queue. With this prior technique, only a single queue-accessing program can change the queue at a time, and simultaneous change operations on the queue are not done.
The prior pure LIFO (last-in/first-out) queueing method does not require any lock associated with the queue anchor when it uses the atomic operation to insert or delete the anchor pointed element. The LIFO queue enables hardware serialization of parallel requests from different programs on plural CPUs to enqueue and dequeue the current anchor pointed element on the single queue, while maintaining the integrity of the queue which is of foremost importance. This solution uses the IBM System/370 CS or CDS instruction directly on the queue anchor pointer to accomplish the element insertion or deletion of the anchor pointed element. Background on this type of use of the Compare and Swap instruction on a queue element is found in the IBM System/370 Principles of Operation (GA22-7000-8) pages 7-12 to 7-14 and its Appendix A pages A40 to A46, in particular the section entitled "Free-Pool Manipulation". The Compare and Swap instruction is provided in two forms for handling either a single word field (CS instruction) or a double word field (CDS instruction); and the size of queue anchor field (i.e. one word or two words) determines the use of CS or CDS for a single element LIFO insertion or deletion operation on a queue. During the CS or CDS instruction execution, no processor in a MP can interfere with an enqueueing or dequeueing operation being done by another processor, provided the field being handled has the one or two word size limitation of the respective instruction, and provided that the instruction is used properly.
All System/370 queue management programs have available the address of the queue anchor pointer as a displacement D2 from the current content of a specified base general register B2. Each queue management routine must then set up the operands for the CS or CDS instruction, which include loading any available general register R1 with the contents of the storage location identified by the effective address of D2(B2), which may be the current anchor pointer content that addresses the first queue element. To insert a LIFO element, the queue management program must initially set up the new element which later is to be inserted in the queue, store the anchor pointer in the element as the element's pointer, and store the address to the element into a general register R3. To delete an element, the queue management program must initially store into a general register R3 the content of the pointer within the anchor pointed element to be deleted from the queue. Then the Compare and Swap instruction CS is executed in an attempt to effect the requested insertion or deletion. When executed, the CS instruction tests R1 to determine if the content of the anchor pointer has changed; and if not changed, the address in R3 is atomically stored into the anchor pointer to cause the insertion or deletion of the anchor pointer element to take place in the queue. If CS or CDS execution finds the anchor pointer has changed since R1 was set up, the insertion or deletion attempt fails, but R1 is reloaded with the current anchor pointer for a next try. A condition code (CC) for the CS instruction indicates if its execution has succeeded or failed.
Nevertheless, experience has taught that some risk still exists for destroying the queue during enqueueing and dequeueing operations when only the anchor pointer is swapped by a CS instruction for an insertion or deletion element in LIFO operations.
The integrity risk is that: (1) while a first program is attempting to dequeue a single element then on the queue after finding the pointer is zero in the anchor pointed element, (2) a second program dequeues that element, inserts a new element, and then reinserts the element it had previously dequeued as a new anchor pointed element, and (3) all before the first program executes its CS instruction. In this case, the first program then executes its CS instruction successfully, because it will compare equal with the reinserted anchor pointer. Unfortunately in this case, the CS instruction of the first program will insert an all zero field in the anchor pointer to indicate an empty queue, because the first program is unaware that another element had been put into the queue in the interim period. That zero anchor pointer destroys the queue because it breaks the pointer chain and thereby ignores the existence of an element on the queue, which is then not empty.
A high risk queue is a useless queue in a high speed data processing system, because queue failure will most likely cause the data processing operation to stop or to produce erroneous results. The detection of this type of software failure may be difficult to find and correct, resulting in expensive down time for the system.
This significant risk to queue integrity has been found in the prior art to be relieved by the addition of a counter field located contiguously with the anchor pointer, in which each is a one word field and they are swapped as a unit by a CDS instruction.
The CS or CDS instruction is followed by a conditional branch instruction which tests the condition code of the executed CS or CDS instruction to determine if the requested element insertion or deletion was successful. If unsuccessful, the routine loops back to again revalidate the R3 content and then re-execute the CS or CDS instruction, and if necessary repeat the looping back until the CS or CDS execution is successful.
The following prior art System/370 assembler language coding taken from the IBM System/370 Principles of Operation provides examples of insertion and deletion queue management routines which include a count value with the anchor pointer, wherein the use of the count value is essential to the integrity of the queue. The CDS instruction allows a word size anchor pointer and a contiguous word size count value to be stored into the queue anchor block as a unit on a successful execution of the CDS instruction.
______________________________________ Element Insertion Routine - Initial Conditions: GR0 will be loaded with the anchor pointer. GR1 will be loaded with the counter value. GR2 contains the address of the element to be added. GR3 will contain the decremented counter value. GR4 contains the address of the anchor pointer. ADDQ LM 0,1,0(4) GR0,GR1 = contents of the anchor pointer and counter. TRYAGN ST 0,0,(2) Point the new element to the current top element in the list. LR 3,1 Move the counter to GR3. BCTR 3,0 Decrement the counter. CDS 0,2,0(4) Update the anchor pointer and counter. BNE TRYAGN Element Deletion Routine - Initial Conditions: GR4 contains the address of the anchor pointer. GR0 will contain the address of the anchor pointed element to be deleted. GR1 will contain the unchanged counter value. GR2 will be loaded with the anchor pointer. GR3 will be loaded with the changed counter value. DELETQ LM 2,3,0,(4) GR2,GR3 = contents of the anchor pointer and counter. TRYAGN LTR 2,2 Is the list empty? BZ EMPTY Yes, get help. L 0,0(2) No, GR0 = the pointer from the last entered element (N). LR 1,3 Move the counter to GR1. CDS 2,0,0(4) Update the anchor pointer and counter. BNE TRYAGN USE (Any Instruction) The address of the removed element is in GR2 = R1. ______________________________________
A CPU is considered to be in the process of inserting or deleting an element on a queue from the time it begins executing an element insertion or deletion routine until an execution of the routine finds the condition code of its CS or CDS instruction to be zero, indicating its insertion or deletion was successful. Thus, several programs on different CPUs in a MP can be simultaneously executing insertion or deletion programs on the same LIFO queue with looping (called "spinning") by some of the routine until the contention ends for each routine when its CS or CDS instruction is executed successfully.
An example of interference can be visualized by having two CPUs concurrently executing queue management routines on the same LIFO queue. Either CPU may be attempting insertion or deletion on the LIFO queue asynchronously in that neither CPU knows that the other is attempting to access the LIFO queue, i.e. there is no synchronizing communication signalling between them. Suppose the first CPU routine has begun execution by setting up its operands, but has not yet executed its CDS instruction when the second CPU routine has successfully executed its CDS instruction to obtain a successful insertion or deletion of the current anchor pointed element, which changes the content of the anchor pointer at storage location D2(B2). Then, when the first CPU routine executes its CDS instruction, it will be unsuccessful because the actual anchor pointer at D2(B2) or the counter, will compare unequal with the previously loaded anchor pointer in R1 or the counter in R1+1. However, the unsuccessful CDS execution will reload R1 with the new actual pointer value in preparation for the next CDS execution attempt by the first CPU. If the actual pointer value and counter at D2(B2) has not changed from the R1 and R1+1 content at the time of the next CDS execution, it will then be successful.
Accordingly, the CDS instruction operation prevents an improper queue change by requiring the existence of all essential conditions in order to maintain the integrity of the queue under interference situations. Prior art queue management programs have been doing these insertion and deletion routines for many years for LIFO queue operation without any lock on the queue, because this type of programming has permitted parallel LIFO insertion and deletion operations by plural programs and CPUs. Unfortunately, this type of unlocked queue operation cannot be used for non-LIFO queue operation, such as FIFO (first-in, first-out) operations.
In the prior art, certain FIFO results have been obtained by using an input queue and an output queue, which duplicate the same elements. The input queue is LIFO for inserting received elements, and the output queue is generated from the input queue, wherein the elements are occasionally rechained in a sorted sequence by values in their priority fields to provide an ordered output queue. This technique has been used in the IEAVEDS0 and IEAVESC1 modules in a prior IBM MVS program. Elements can be inserted efficiently on the input queue by plural CPUs without queue integrity loss without locking the input queue by using the above described compare and swap techniques for inserting each new element as a new anchor pointed element in the input queue, as explained above for LIFO element insertion. The output queue is generated when certain conditions occur (e.g. maximum input queue size is reached or the output queue is empty), and both queues are locked (which prevents further use of both queues) while all elements of the input queue are put into an ordered sequence from the output queue anchor to generate the output queue, leaving the input queue empty and ready to receive new elements. The output queue always operates with a lock to prevent insertion, but allows ordered dequeueing (deletion) without using a dequeueing lock by dequeueing from the anchor pointed element. The prevention of use of both of these queues during their occasional reorganization is a system liability because it may cause temporary suspension of some system operations during queue reorganization.
Another prior queue control method is described and claimed in U.S. Pat. No. 4,482,956 to P. H. Tallman, and assigned to the same assignee as the present invention. It enables parallel operations in a single chained queue by element insertion routines that are simultaneously executing on plural processors while an element deletion routine on any processor may be simultaneously removing any element on the queue. That is, in a single chained queue in storage, one processor in an MP may execute a programmed routine for finding and deleting any element in combination with any number of other processors simultaneously executing programmed routines for inserting anchor pointed elements. An anchor associated dequeueing lock is set on for serializing the deletion processing to one element at a time but does not affect simultaneous parallel processing of one or more routines for enqueueing anchor pointed elements.
Also, in U.S. Pat. No. 4,482,956 the non-LIFO locked dequeueing processing of a non-anchor pointed element involved searching the queue (beginning with the anchor pointer) for the requested element and outputting the pointer to it in its prior element in the queue sequence as the address of the dequeued element. Then it is dequeued by moving into the prior element the pointer within the dequeued element. This deletes the dequeued element from the queue by changing its prior element pointer to address the queue element that followed the dequeued element in the queue sequence. The locked dequeueing of an anchor pointed element involves changing the anchor pointer to address the queue element that followed the anchor pointed element being dequeued in the queue sequence, and outputting the address of the anchor pointed element being dequeued.
An important special case of non-LIFO processing is FIFO (first-in/first-out) processing which finds the last element in the queue as the required element. The last element is conventionally identified by an end-of-queue code in its pointer field, which is looked for and dequeued during a FIFO operation. U.S. Pat. No. 4,482,956 provides efficient processing in a non-pure LIFO queue, which is non-pure because the queue can, at the user's option, be used for either LIFO or non-LIFO dequeueing. It does not use any lock on the queue when inserting anchor pointed elements on the queue, for which queue integrity is maintained by using the System/370 compare and swap instruction in a manner similar to the way this instruction has been used in the prior art for inserting and deleting anchor-pointed elements in prior pure LIFO queues.
A prior shared/exclusive locking method for MP of a different type than the subject invention is disclosed in an article entitled "Shared Locking Without A Lock" by M. Taradalsky on page 1545 of Vol. 18, No. 5, October 1975 of the IBM Technical Disclosure Bulletin. This queue also serializes all requests for changing the queue, so that only one can change it at a time, although multiple parallel read requests can be handled.
Still another prior queue control method is described and claimed in U.S. Pat. No. 4,604,694 to R. E. Hough and assigned to the same assignee as the present invention. It provides a unique shared/exclusive queue for resource control in a MP system. It also uses an anchor associated lockword in its method for controlling both shared and exclusive access for a resource in a MP system, wherein a FIFO queue is formed for tasks suspended while awaiting access to the resource. The lockword is established having two parts, a lock flag indicating the status of the resource, whether available, under shared ownership or under exclusive ownership, and a lock (i.e. anchor pointer) pointing to the most recently enqueued task. In requesting or releasing access, an initial guess is made as to the value of the lockword and a projected lockword is calculated based on the guess. Then an atomic reference is made to the lockword during which no other processor has access to the lockword. During the atomic reference, the lockword is compared to the guess of the lockword and if the guess is correct, the lockword is replaced by the projected lockword which rearranges the queue for the requesting or releasing task. If the guess was incorrect, the value of the lockword is used to calculate another projected lockword. If another task can affect the next tasks to gain access, the process with the atomic reference is repeated until no intervening changes occur between atomic references.
The prior filed U.S. patent application entitled "Extended Atomic Operations" by R. Obermarck et al Ser. No. 787,221, 10/15/85, and assigned to the same assignee as the present invention, discloses a queue which allows a plurality of requestors to add to the one end of a queue and to output from the other end of the queue which maintains the received order. Atomic operations are used for enqueueing and dequeueing only one element at a time. A counter protocol is disclosed for managing the queue, and a search of the queue is used for finding the oldest element to dequeue. The counter protocol uses a request counter associated with the queue header for adding elements to the queue, and a credit counter used for serializing the dequeueing of elements one at a time. Unlike the subject application, the Obermarck et al. application does not allow for inserting an element anywhere in the queue, for deleting an element anywhere in the queue, or for plural concurrent queue element deletions.
Prior IBM MVS programs have used a dispatching queue which is a chained hierarchical queue with a second level queue access lock field in each of first-level elements of the queue to control the serialization of accesses to each element's associated second level queues. The first-level elements are address space control blocks (ASBBs) which contain both forward pointers and backward pointers in relation to the queue's anchor element. The two second level queues are a system request block (SRB queue and a task control block (TCB) queue associated with each ASCB: and their order of search is to first search the SRB queue and then the TCB queue for a dispatchable block. The task control block (TCB) is an ordered queue. The queue is a LIFO queue comprised of system request blocks (SRBs). The second level blocks are in active or wait states to control CPU dispatching in an MP system.
In the prior MVS dispatching queue, the first-level elements are left permanently on the queue as long as they are in main memory. They are only deleted from queue when they are swapped out of main memory to auxiliary storage. They are reinstated into the queue when they are swapped back into main memory. Whether or not an element has all of its blocks non-dispatchable (in wait state) has no effect on whether or not the element is deleted from or inserted in the queue. The first-level elements remain in the queue regardless of whether any associated second level block is dispatchable, even when all associated second level blocks are inactive in I/O wait state.
The prior hierarchical queue has a queue anchor through which the queue is accessed by a dispatching program on any CPU in the system. A pointer in the anchor locates the first of the first-level elements of the queue (which is associated with the highest-priority second level blocks) and is chained in a priority sequence to the other first level elements. (See prior cited IBM Technical Disclosure Bulletin article by M. Taradalsky.
Different processes (and processors) may be simultaneously searching through the first level elements in the queue including simultaneously accessing the same first level element.
As systems have gotten larger and more powerful (executing 10's of millions of instructions per second with multiple CPU's in a system), the dispatching queue has grown to large size, sometimes having hundreds of first level elements. This results in long serecjtimes in the queue for finding the next task to dispatch on each of the various one or more CPU's in the system, since the search may need to examine a great number of higher level first level elements before it can find the first dispatchable block at some lower priority level. The second-level blocks may or may not be chained priority sequence in their sets. This increase in queue length has substantially increased the dispatching overheard in large systems.